A block of memory may be allocated for use by a program executing in a computer system. The block of memory is typically referred to as a heap. The heap may be further divided into fixed size pages. The program requests a portion of memory from the heap when needed, for example, to store an object such as an array.
A garbage collector, also referred to as automatic storage reclamation, manages the heap by reclaiming memory no longer required by the program. Typically, the garbage collector is executed if a currently executing program is unable to allocate memory for new objects because all the allocatable memory has been allocated to other objects. Garbage collection is required by computer programming languages such as LISP™, Java™, SmallTalk™ and ML™. Garbage collection can also be used by programing languages such as C and C++.
In order to determine which objects may be collected, the garbage collector traverses all pointers to objects reachable from the processor's call stack and registers. Objects reachable from the processor's call stack are considered non-collectable because there are currently being used. All the objects in the heap that are not reachable from the processor's call stack are collectable because they are no longer in-use and are thus garbage. The collectable objects are collected for future allocations.
Techniques for garbage collection include reference counting, mark-sweep collection and copying collection. The reference counting technique stores a reference count for each object stored in the heap equal to the number of pointers pointing to the object. The reference count is stored in a header field in the object. Objects may be reclaimed if the reference count is zero. However, the reference counting technique decreases the performance of the program because the cost of reference counting is proportional to the number of pointer stores. Also, cycles of garbage cannot be reclaimed by the garbage collector.
The mark-sweep collection technique marks all reachable objects. Reachable objects may be marked by setting a bit in the header field of each reachable object. After reachable objects are marked, the unmarked objects are stored in memory in a doubly-linked free list. Subsequently, memory is allocated by removing objects from the free list.
The copying collection technique divides the heap into two contiguous regions; a first region and a second region. Memory is allocated for an object from a first region. When all the memory in the first region is in use by the program, reachable objects are copied from the first region to a second region. The roles of the first region and the second region are reversed. This effectively provides available memory, for allocation purposes, from the end of the new first region formerly called the second region. However, the time taken to copy large objects from a first region to a second region can consume a large portion of the total program execution time.
Garbage collection can consume a portion of the total program execution time. In some object oriented programming languages, such as Java™, the garbage collector may occasionally consume as much as fifty percent of program execution time because collection is required to reclaim memory from the heap for the executing program.
Techniques are available for reducing the amount of program execution time consumed by the garbage collector for copying objects. One such method is age-based generational collection. An age-based garbage collector segregates objects into old and young objects dependant on the time at which memory was allocated for the object. The assumption is that memory allocated for young objects can usually be freed before memory allocated for old (longer lived) objects. Thus, the age-based generational collector collects the youngest objects; that is, those more recently having memory allocated to them. By doing so, long-lived-objects are not copied. By collecting only the youngest objects, the program execution time consumed by garbage collection is reduced.
However, age-based generational collection is not always appropriate for computer languages such as Java™. Java™ frequently updates long-lived objects, for example, by adding data to elements of an array. This updating may result in excessive copying which consumes program execution time.
Thus, various disadvantages exist in currently existing garbage collection techniques/methods and there is a need for improvement in garbage collecting.